Notes (Week 2 Wednesday)
These are the notes I wrote during the lecture.
*Relations*
are sets of tuples.
*Functions*
are sets of tuples (but with some special properties)
think: input-output pairs
Q: Are relations similar to simple formulae?
A: Yes (spoiler alert)
Think: simple formulae are *syntax*,
which we can give meaning using relations.
For example:
We've said already that ≤ (let's say on ℕ)
is a relation.
More formally, we can think of it as a
set of pairs of numbers.
(≤) ⊆ ℕ × ℕ
What we would normally write as x ≤ y,
we could instead write as (x,y) ∈ (≤)
(we'll use these interchangably)
(≤) = {(x,y) ∈ ℕ × ℕ | ∃z∈ℕ. x + z = y}
We'll write membership in a relation in three ways:
x R y x ≤ y
R(x,y) (≤)(x,y)
(x,y) ∈ R (x,y) ∈ (≤)
Q: Isn't it a bit circular to consider membership as a relation,
when relations themselves are defined by membership?
A: Yes. This would mainly show up if you have a smaller set theory in
your big set theory. (But this won't really show up in this course)
We can (if we so choose) form the Cartesian product of one set S.
This product is exactly S.
The unary relations over S are just the subsets of S.
We can think of the set of people enrolled in COMP2111 as a
unary relation over the set of all people.
Relational image.
You might want to ask: for a given element x, can you give me
everything that is related to x by the relation R?
That's what relational image is (but lifted to sets)
R = (≤) ⊆ ℕ × ℕ
R({1}) "everything that is related to 1 by ≤"
"everything x s.t. 1 ≤ x"
R({1}) = {1,2,3,4,5,6,...}
S ⊆ ℕ × ℕ
S = {(x,y) | y = x+1}
(1,2) ∈ S (1,3) ∉ S .....
S({1,2,3}) = {2,3,4}
S(ℕ) = ℕ - {0}
S(S(ℕ)) = ℕ - {0,1}
Q: By convention do we always take the image from left to right?
A: Yes! There's a thing for right to left too, it's called inverse image
but we don't really use it
Converse relations.
Every relation has a converse.
Intuitively: the same relation, except oriented left to right
instead of right to left
≤ is the converse of ≥
If R ⊆ S × T then
the converse of R, written R^←
is a relation R^← ⊆ T × S
R^← = {(t,s) | (s,t) ∈ R}
Q: What's the negation of a relation?
A: Its set complement.
Q: Does the graph only make sense when the relation goes from S to S?
A: Yes, but if you have an S × T relation you can draw that as a
bipartite graph
Q: Is the identity relation the same thing as a reflexive relation?
A: They're related concepts.
The identity relation is reflexive, but not every reflexive relation
is the identity relation.
(x,y),(y,x) ∈ R ⇒ x = y
^ if we choose R ≡ (=)
x = y ∧ y = x ⇒ x = y <--- that's a tautology
(an instance of A ∧ B ⇒ A)
Q: Are we assuming that ∅ is between two non-empty sets?
A: In this slide (#58), yes
The domain of a relation is considered part of its definition
∅ ⊆ ℕ × ℕ (1)
would be different from
∅ ⊆ ℝ × ℝ (2)
What about ∅ ⊆ ∅ × ∅ (3)
^ curiouly, ∅ (3) is reflexive, but ∅ (1) and (2) are not reflexive.
∀x ∈ ℕ. (x,x) ∈ ∅ <----- clearly false
∀x ∈ ∅. (x,x) ∈ ∅ <----- (vacuously true)
∀x y. x ≤ y ∧ y ≤ x ⇒ x = y <--- this is true,
but not vacuously true.
Intuitively: its truth depends on the
meaning of the predicate symbols used
(the meaning of ≤)
If it was vacuously true, we should be able to replace ≤ with another relation
and still have the thing hold
∀x y. R(x, y) ∧ R(y, x) ⇒ x = y
In an anti-reflexive relation,
nothing relates to itself ∀x. (x,x) ∉ R
In a non-reflexive relation,
not everything relates to itself ∃x. (x,x) ∉ R
In an anti-symmetric relation,
no relation goes both ways. ∀x y. (x,y) ∈ R ⇒ (y,x) ∉ R
In a non-symmetric relation,
not every relation goes both ways. ∃x y. (x,y) ∈ R ⇒ (y,x) ∉ R
There's two things called posets.
Strict posets
Relations that are antireflexive, antisymmetric and transitive
Non-strict posets
Relations that are reflexive, antisymmetric and transitive
^ When slide 62 says "poset", it means "non-strict poset"
≼ pronounced "precedes"
on slide 62, we use this symbol as though it was a variable name
denoting an arbitrary partial order
Q: Why does (ℕ,|) count as poset, but not (ℤ,|).
A: Negative numbers break antisymmetry
Intuitively:
a minimum element is above nothing
the minimal element (if one exists)
is below everything
For example:
(ℤ, ≤) <--- this one has no minimal elements, and no maximal elements
because we can always find a bigger or smaller number
(ℕ, ≤) <--- this one has a minimal (minimum) element but no maximal
Q: is it true for every totally ordered set that minimal element are always
minimum elements?
A: Suppose there are two minimal elements x and y.
If the relation is total, we must have either x R y or y R x
Then, either x = y (in which case there aren't actually two)
or x ≠ y (in which case we've found a counterexample to antisymmetry)
Intuitively:
functions f from S to T are relations
f ⊆ S × T
that relate everything in S to exactly one thing in T.
f(x) = y
if we think of functions as relations, we could also write:
(x,y) ∈ f
f(x) = x+2
we can think of f as a relation
f = {(0,2),(1,3),(2,4),...}
^ this relation is a function because
(a) the LHS of the pairs covers the whole domain
(b) for every LHS there is a unique RHS
here's something that's not a function:
R = {(0,2),(0,3),....} (because the output for a given input
must be unique)
f : ℕ → ℕ
^ domain ^ codomain
f(x) = x + 2
The *image* is the "actual outputs"
The image of f is ℕ - {0,1}
g ∘ f "the function composition of g and f"
(g ∘ f)(x) = g(f(x))
f : ℕ → ℕ
^ f would be surjective if every number is actually returned by f
(for some input)
f(war) = aware
^ not surjective because not every word starts with a and ends with e